# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return str(self.val)


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        slow = head
        fast = head
        while fast.next:
            if fast.next is None:
                break
            elif fast.next.next is None:
                fast = fast.next
                break
            fast = fast.next.next
            slow = slow.next

        p1 = slow.next
        slow.next = None
        p2 = p1.next
        p1.next = None
        while p2:
            tmp = p2.next
            p2.next = p1
            p1, p2 = p2, tmp
        fastHead = p1
        while fastHead:
            if fastHead.val != head.val:
                return False
            fastHead = fastHead.next
            head = head.next
        return True


def buildTreeNode(nodes):
    print(nodes)
    a = []
    for val in nodes:
        a.append(ListNode(val))

    for i in range(len(a) - 1):
        a[i].next = a[i + 1]
    return a[0]


if __name__ == '__main__':
    so = Solution()
    s = [1,0,3,4,0,1]
    s = buildTreeNode(s)
    r = so.isPalindrome(s)
    print(r)
